package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_117_填充每个节点的下一个右侧节点指针II {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_117_填充每个节点的下一个右侧节点指针II().connect(new Node()));
    }

    /**
    题目：给定一个二叉树
     struct Node {
     int val;
     Node *left;
     Node *right;
     Node *next;
     }
     填充它的每个 next 指针，让这个指针指向其下一个右侧节点。
     如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     初始状态下，所有 next 指针都被设置为 NULL。

     进阶：
     你只能使用常量级额外空间。
     使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

     示例：
     输入：root = [1,2,3,4,5,null,7]
     输出：[1,#,2,3,#,4,5,7,#]
     解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

    分析：【P 💜💜💜】
       1.递归：先序遍历 + 用list记录每一层的最后一个节点
            -- 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.
     **/
    public Node connect(Node root) {
        List<Node> ceng = new ArrayList<>();
        dfs(root,ceng,1);
        return root;
    }

    private void dfs(Node root, List<Node> ceng, int x) {
        if(root==null) return;
        if(ceng.size()<x){
            ceng.add(root);
        }else {
            ceng.get(x-1).next=root;
            ceng.set(x-1,root);
        }
        dfs(root.left,ceng,x+1);
        dfs(root.right,ceng,x+1);
    }
}
